package quickSort;

import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA
 * Details about unstoppable_t:
 * User: Administrator
 * Date: 2021-02-01
 * Time: 14:40
 * 快速排序 非常重要
 */
public class TestDemo {
    public static void main(String[] args) {
        int[] array = {10,3,2,7,19,78,65,127};
        System.out.println("非递归快速排序前: "+ Arrays.toString(array));
//        int[] array1 = new int[10000];
//        for (int i = 0; i < array1.length; i++) {
//            array1[i] = i;
//        }
//        long currentime = System.currentTimeMillis();
        quickSort1(array);
//        long endTime = System.currentTimeMillis();
//        System.out.println(currentime - endTime);
        System.out.println("非递归快速排序后: "+Arrays.toString(array));

    }

    //优化
    public static void medianOfTree(int[] array, int low, int high){
        int mid = (low + high)/2;
        //选择基准值 目的：让array[mid] <= array[low] <= array[end]
        if(array[low] < array[mid]){
            int tmp = array[low];
            array[low] = array[mid];
            array[mid] = tmp;
        }
        if(array[low] > array[high]){
            int tmp = array[low];
            array[low] = array[high];
            array[high] = tmp;
        }
        if(array[mid] > array[high]){
            int tmp = array[mid];
            array[mid] = array[high];
            array[high] = tmp;
        }
    }

    public static int pivot(int[] array, int start, int end){

        int tmp = array[start]; //将start的值给中间变量tmp
        while(start < end){
            while(start < end && array[end] > tmp){
                end--;
            }
            //当不满足start<end，即后面元素都比tmp大，end一直走到第一个下标，直接break
            if(start >= end){
                break;
            //因为不满足array[end]>array[start],循环退出，此时把end的值赋值给start
            }else{
                array[start] = array[end];
            }

            while(start < end && array[start] < tmp){
                start++;
            }
            if(start >= end){
                break;
            }else{
                array[end] = array[start];
            }
        }
        array[start] = tmp;
        return start; //要寻找的基准值
    }

    //快排递归解法
    public static void quickSort(int[] array, int low, int high){
        //if(low >= high) return;也是可以的
        if(low < high){
//            medianOfTree(array,low,high); //选基准值
            //优化：在趋于有序时，采用插入排序
            if(high - low + 1 <= 50){
                //使用插入排序
                return ; //表明排序已经结束
            }
            int center = pivot(array,low,high);
            pivot(array,low,center-1); //对基准值左边分治
            pivot(array,center+1,high); //对基准值右边分治
        }
    }



    //快速排序非递归方法
    public static void quickSort1(int[] array){
        Stack<Integer> stack = new Stack<>();
        int low = 0;
        int high = array.length - 1;
        int piv = pivot(array,low,high);

        if(piv > low+1){
            stack.push(low);
            stack.push(piv-1);
        }
        if(piv < high-1){
            stack.push(piv+1);
            stack.push(high);
        }
        while(!stack.empty()){
            //弹出两个元素，作为新的high和low
            high = stack.pop();
            low = stack.pop();
            piv = pivot(array,low,high);

            if(piv > low+1){
                stack.push(low);
                stack.push(piv-1);
            }
            if(piv < high-1){
                stack.push(piv+1);
                stack.push(high);
            }

        }
        //循环退出，栈为空，排序完成
    }

}
